package com.LeeCode;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 出现次数最多的子树元素和
 */

public class Code508 {
    public static void main(String[] args) {
        Integer[] arr = {5, 2, -3};
        TreeNode root = Utils.buildTree(arr);
        System.out.println(Arrays.toString(new Code508().findFrequentTreeSum(root)));
    }

    private int maxCount = 0;

    public int[] findFrequentTreeSum(TreeNode root) {
        HashMap<Integer, Integer> map = new HashMap<>();
        dfs(root, map);

        return map.entrySet().stream()
                .filter(e -> e.getValue() == maxCount)
                .mapToInt(Map.Entry::getKey)
                .toArray();
    }

    private int dfs(TreeNode root, Map<Integer, Integer> map) {
        if (root == null) return 0;
        int left = dfs(root.left, map), right = dfs(root.right, map);
        int sum = root.val + left + right;
        map.merge(sum, 1, Integer::sum);
        maxCount = Math.max(maxCount, map.getOrDefault(sum, 0));
        return sum;
    }
}
